package arithmetic.demo25;

import java.util.HashMap;
import java.util.Map;

/**
 * 动态规划： 含义dp + 二维背包： 一和零
 */
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // 动态规划 + 二维背包
        int len = strs.length;

        // 先统计
        // key = index , value 表示 0 和 1 的个数
        Map<Integer,int[]> hash = new HashMap<>();
        for(int i = 0; i < len; i++) {
            int zero = 0, one =  0;
            for(int j = 0 ; j < strs[i].length(); j++) {
                if(strs[i].charAt(j) == '0') {
                    zero++;
                } else {
                    one++;
                }
            }
            // 加入哈希
            hash.put(i,new int[]{zero, one});
        }
        // 创建 dp
        int[][][] dp = new int[len+1][m+1][n+1];

        // 填表
        for(int i = 1; i <= len; i++) {
            int[] tmp = hash.get(i - 1);
            for(int j = 0; j <= m; j++) {
                for(int k = 0; k <= n; k++) {
                    // 先继承前面的
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= tmp[0] && k >= tmp[1]) {
                        dp[i][j][k] = Math.max(dp[i][j][k],
                                dp[i-1][j-tmp[0]][k-tmp[1]] + 1);
                    }
                }
            }
        }

        return dp[len][m][n];
    }
}

/**
 * 动态规划： 含义dp + 二维背包： 一和零（优化版）
 */

class Solution1 {
    public int findMaxForm(String[] strs, int m, int n) {
        // 动态规划 + 二维背包
        int len = strs.length;

        // 先统计
        // key = index , value 表示 0 和 1 的个数
        Map<Integer,int[]> hash = new HashMap<>();
        for(int i = 0; i < len; i++) {
            int zero = 0, one =  0;
            for(int j = 0 ; j < strs[i].length(); j++) {
                if(strs[i].charAt(j) == '0') {
                    zero++;
                } else {
                    one++;
                }
            }
            // 加入哈希
            hash.put(i,new int[]{zero, one});
        }
        // 创建 dp
        int[][] dp = new int[m+1][n+1];

        // 填表
        for(int i = 1; i <= len; i++) {
            int[] tmp = hash.get(i - 1);
            for(int j = m; j >= tmp[0]; j--) {
                for(int k = n; k >= tmp[1]; k--) {
                    dp[j][k] = Math.max(dp[j][k],
                            dp[j-tmp[0]][k-tmp[1]] + 1);

                }
            }
        }

        return dp[m][n];
    }
}

/**
 * 动态规划： 含义dp + 二维背包： 一和零（最终优化版）
 */


class Solution2 {
    public int findMaxForm(String[] strs, int m, int n) {
        // 动态规划 + 二维背包
        int len = strs.length;

        // 先统计
        // key = index , value 表示 0 和 1 的个数

        // 创建 dp
        int[][] dp = new int[m+1][n+1];

        // 填表
        for(int i = 1; i <= len; i++) {
            int zero = 0, one =  0;
            for(int j = 0 ; j < strs[i-1].length(); j++) {
                if(strs[i-1].charAt(j) == '0') {
                    zero++;
                } else {
                    one++;
                }
            }

            for(int j = m; j >= zero; j--) {
                for(int k = n; k >= one; k--) {
                    dp[j][k] = Math.max(dp[j][k],
                            dp[j-zero][k-one] + 1);

                }
            }
        }

        return dp[m][n];
    }
}


/**
 * 动态规划: 含义dp + 二维费用的01背包问题； 盈利计划
 */

class Solution3 {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        // 动态规划 + 多维背包
        int len = group.length;
        int MOD = (int)(1e9 + 7);

        // 创建 dp
        int[][][] dp  = new int[len+1][n+1][minProfit+1];

        // 初始化
        dp[0][0][0] = 1;


        for(int j = 0; j <= n; j++) {
            dp[0][j][0] = 1;
        }

        // 填表
        for(int i = 1; i <= len; i++) {
            for(int j = 0; j <= n; j++) {
                for(int k = 0; k <= minProfit ; k++) {
                    // 先继承前面的
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= group[i-1]) {
                        // 加上这一列
                        // 并且如果 超过这个最小值的话
                        // 我们就取刚好等于最小值 --> k - profit[i-1] = 0
                        dp[i][j][k] += dp[i-1][j - group[i-1]][Math.max(0,k-profit[i-1])];
                    }
                    // 防止溢出
                    dp[i][j][k] %= MOD;
                }
            }
        }

        return dp[len][n][minProfit] ;
    }
}

/**
 * 动态规划: 含义dp + 二维费用的01背包问题； 盈利计划（优化版）
 */

class Solution4 {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        // 动态规划 + 多维背包
        int len = group.length;
        int MOD = (int) (1e9 + 7);

        // 创建 dp
        int[][] dp = new int[n + 1][minProfit + 1];

        // 初始化
        dp[0][0] = 1;

        for (int j = 0; j <= n; j++) {
            dp[j][0] = 1;
        }

        // 填表
        for (int i = 1; i <= len; i++) {
            for (int j = n; j >= group[i - 1]; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    // 加上这一列
                    // 并且如果 超过这个最小值的话
                    // 我们就取刚好等于最小值 --> k - profit[i-1] = 0
                    dp[j][k] += dp[j - group[i - 1]][Math.max(0, k - profit[i - 1])];
                    // 防止溢出
                    dp[j][k] %= MOD;
                }
            }
        }

        return dp[n][minProfit];
    }
}